//给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。 
//
// 两个相邻元素间的距离为 1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：
//[[0,0,0],
// [0,1,0],
// [0,0,0]]
//
//输出：
//[[0,0,0],
// [0,1,0],
// [0,0,0]]
// 
//
// 示例 2： 
//
// 
//输入：
//[[0,0,0],
// [0,1,0],
// [1,1,1]]
//
//输出：
//[[0,0,0],
// [0,1,0],
// [1,2,1]]
// 
//
// 
//
// 提示： 
//
// 
// 给定矩阵的元素个数不超过 10000。 
// 给定矩阵中至少有一个元素是 0。 
// 矩阵中的元素只在四个方向上相邻: 上、下、左、右。 
// 
// Related Topics 广度优先搜索 数组 动态规划 矩阵 
// 👍 452 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    int[][] steps = new int[][]{
            {0,1},
            {0,-1},
            {1,0},
            {-1,0},
    };

    /*
    Time Limit Exceeded
    测试用例:[[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[0,0,0]]
     */
    public int[][] updateMatrix(int[][] mat) {
        int[][] ret = new int[mat.length][mat[0].length];
        //多源广搜
        Queue<Data> queue = new LinkedList<>();
        //给所有的0，初始化distance，所有1的初始化distance为最大值
        //将所有的0，加入到广搜状态集合中
        for(int i=0; i<mat.length; i++){
            for(int j=0; j<mat[i].length; j++){
                if(mat[i][j] == 0){
                    ret[i][j] = 0;
                    queue.add(new Data(i,j,0));
                }else{
                    ret[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        //以0为源头，扩散找1，如果找到的距离更小，那么更新这个距离值
        while (!queue.isEmpty()){
            Data data = queue.poll();
            for(int[] step : steps){
                int x = data.i + step[0];
                int y = data.j + step[1];
                if(x < 0 || x >= mat.length ) continue;;
                if(y < 0 || y >= mat[0].length) continue;;
                if(1 == mat[x][y]){
                    int curDist = data.dist+1;
                    if(curDist < ret[x][y]){
                        queue.add(new Data(x,y,curDist));//剪枝优化，小于的才有必要再搜索下去
                        ret[x][y] = curDist;
                    }
                }
            }
        }

        return ret;
    }
    class Data{
        int i,j,dist;

        public Data(int i, int j, int dist) {
            this.i = i;
            this.j = j;
            this.dist = dist;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
